package lc;

/**
 * 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
 */
public class QM1719 {

    public int[] missingTwo(int[] nums) {
        int[] others = new int[2];
        for (int i = 0; i < nums.length; i++) {
            final int num = nums[i];
            // 将num放入正确的位置
            if (num == nums.length + 1) {
                others[0] = num;
            } else if (num == nums.length + 2) {
                others[1] = num;
            } else {
                if (num != i + 1) {
                    nums[i] = nums[num - 1];
                    nums[num - 1] = num;
                    i --;
                }

            }
        }
        // 扫描寻找第一个不匹配的
        int first = -1;
        int second = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                // 这是一个
                if (first == -1) {
                    first = i + 1;
                } else {
                    second = i + 1;
                }
                if (second != -1) {
                    break;
                }
            }
        }
        if (second == -1) {
            for (int i = 0; i < others.length; i++) {
                if (others[i] - nums.length != i+1) {
                    if (first == -1) {
                        first = nums.length + i + 1;
                    } else {
                        second = nums.length + i + 1;
                    }
                    if (second != -1) {
                        break;
                    }
                }
            }
        }
        return new int[]{first, second};
    }

    public static void main(String[] args) {
        final QM1719 qm1719 = new QM1719();
        final int[] ints = qm1719.missingTwo(new int[]{1, 2, 3, 4, 6, 7, 9, 10});
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }


}
